691D - Swaps in Permutation - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define s second
#define f first

void helper(int vis[], vector<int>list[], int i, vector<int>&comp){
   
   vis[i]= true;
   comp.push_back(i);

   for(auto it: list[i]){
    if(vis[it]==false){
     helper(vis, list, it, comp);
   }}
}


void solve(){
int n, t;
cin>>n>>t;
int temp[n+1];
unordered_map<int, int>mp;
for(int i=1; i<=n; i++){
cin>>temp[i];
mp[temp[i]]=i;
}
// sort(temp+1, temp+n+1);
// for(int i=1; i<=n; i++){
// // cin>>temp[i];
// mp[temp[i]]=i;
// }
// for(auto it: mp){
// cout<<it.first<<" "<<it.second<<endl;}
int arr[n+1];
memset(arr, -1, sizeof(arr));

vector<int> list[n+1];

for(int i=0; i<t; i++){
int u, v;
cin>>u>>v;
if(u==v)continue;

list[temp[v]].push_back(temp[u]);
list[temp[u]].push_back(temp[v]);
}


int vis[n+1]={0};
for(int i=1; i<=n; i++){

 if(vis[i]==0){
 vector<int>comp;
 helper(vis, list, i, comp);
 sort(comp.begin(), comp.end());
  vector<int>help;
 for(int j=0; j<comp.size(); j++){ 
help.push_back(mp[comp[j]]);
 }

// for(int s=0; s<comp.size(); s++){
// cout<<comp[s]<<" ";}cout<<"\n";
// for(int s=0; s<comp.size(); s++){
// cout<<help[s]<<" ";}cout<<"\n";



sort(help.begin(), help.end());
 for(int j=0; j<comp.size(); j++){ 
  // cout<<comp[j]<<" "; 
  temp[help[j]]=comp[comp.size()-1-j];
 }

 // cout<<endl;
//   for(int k=1; k<=n; k++){
//     cout<<temp[k]<<" ";}

// cout<<"\n";  
 
}
}
 for(int k=1; k<=n; k++){
    cout<<temp[k]<<" ";}

cout<<"\n";  


}




int32_t main(){
    
    ios_base::sync_with_stdio(false);
        cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE

    int t=1;
    // cin>>t;
    while(t--){
        solve();
    } 
    return 0;
}